import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 433. 最小基因变化
 * https://leetcode.cn/problems/minimum-genetic-mutation/description/
 */
class Solution2 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> vis = new HashSet<>();//标记已经检查过的状态
        Set<String> hash = new HashSet<>();//标记基因库里面的字符串

        //把基因库里的字符串都存进hash表里
        for (String s : bank) hash.add(s);
        char[] change = {'A', 'C', 'G', 'T'};

        //处理边界情况
        if (startGene.equals(endGene)) return 0;
        if (!hash.contains(endGene)) return -1;

        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step = 0;

        while (!q.isEmpty()) {
            step++;
            int sz = q.size();
            while (sz-- != 0) {
                String t = q.poll();
                for (int i = 0; i < 8; i++) {
                    char[] tmp = t.toCharArray();
                    for (int j = 0; j < 4; j++) {
                        tmp[i] = change[j];
                        String next = new String(tmp);
                        if (hash.contains(next) && !vis.contains(next)) {
                            if (next.equals(endGene)) return step;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}